package newBee.class2;

import common.ArrayUtils;

/**
 * 单调队列
 * 维持滑动串口的最大值或最小值
 * <p>
 * https://leetcode.cn/problems/sliding-window-maximum/
 * 滑动窗口最大值
 * <p>
 * 从 大 -> 小
 * *    h ->  t    当 t <= arr[i]时，进行出队列
 * *  -------------------
 * * | 大 -> 小
 * *  -------------------
 */
public class Code01_maxSlidingWindow {
    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] ans = maxSlidingWindow(arr, k);
        ArrayUtils.printArr(ans);
    }

    // 无注释
    public static int[] maxSlidingWindow(int[] arr, int k) {
        int h = 0, t = 0, n = arr.length;
        int[] deque = new int[n];
        for (int i = 0; i < k - 1; i++) {
            while (h < t && arr[deque[t - 1]] <= arr[i]) {
                t--;
            }
            deque[t++] = i;
        }
        int[] ans = new int[n - k + 1];
        int l = 0, r = k - 1;
        for (; r < n; l++, r++) {
            while (h < t && arr[deque[t - 1]] <= arr[r]) {
                t--;
            }
            deque[t++] = r;
            ans[l] = arr[deque[h]];
            if (deque[h] == l) {
                h++;
            }
        }
        return ans;
    }

    /**
     * 收集滑动窗口的最大值 注释版
     */
    public static int[] maxSlidingWindow2(int[] arr, int k) {
        int h = 0, t = 0, n = arr.length;
        int[] deque = new int[n];
        for (int i = 0; i < k - 1; i++) {
            // 队尾小于入队值
            while (h < t && arr[deque[t - 1]] <= arr[i]) {
                t--;
            }
            deque[t++] = i;
        }
        int[] ans = new int[n - k + 1]; // n - k + 1 为可以计算出可能获得多少最大值的数组
        int l = 0, r = k - 1;  // 滑动窗口
        for (; r < n; l++, r++) {
            while (h < t && arr[deque[t - 1]] <= arr[r]) {
                t--;
            }
            deque[t++] = r;
            // 队列的头部索引就是当前窗口的最大值所在位置，记录该最大值
            ans[l] = arr[deque[h]];

            // 当 deque[h] == l 时，意味着队列头部的元素已经超出当前窗口的范围，我们就需要把它移出队列。
            // h 是队列的头指针，指向队列中当前窗口的最大值的索引。
            // l 是窗口的左边界的索引。
            // 再次说明：窗口需要右移 l需要+1，如果l
            if (l== deque[h]) {
                h++;  // 如果队首元素不在窗口内，移除队首元素
            }
        }
        return ans;
    }


}
